The present invention concerns a coding device, a coding method, a decoding device and method and systems implementing them.
It applies just as well to the coding of data representing a physical quantity, to the coding of data in the form of codes able to modulate a physical quantity, to the decoding of data modulated signals, and to the decoding of data representing a physical quantity. These data can for example represent images, sounds, computer data, electrical quantities or stored data.
The invention finds an application in the field of convolutional codes. When the latter are used to implement an iterative decoding, these codes are greatly improved when their coders contain a permutation device. In this case, they are normally referred to as xe2x80x9cturbocodesxe2x80x9d and the corresponding iterative decoder is referred to as a xe2x80x9cturbodecoderxe2x80x9d.
On these subjects, documents which serve as a reference are, on the one hand, the article by Messrs. C. BERROU, A. GLAVIEUX and P. THITIMAJSHIMA entitled xe2x80x9cNear Shannon limit error-correcting coding and decoding: turbocodesxe2x80x9d published with the reports of the conference xe2x80x9cICC""93xe2x80x9d, 1993, pages 1064 a 1070, and, on the other hand, the article by Messrs. C. BERROU and A. GLAVIEUX entitled xe2x80x9cNear Optimum error-correcting coding and decoding: turbo-codesxe2x80x9d published by IEEE Transactions on Communication, Volume COM-44, pages 1261 to 1271, in October 1996.
However, the formation of permutation devices is far from being perfectly mastered. In general this device uses square or rectangular matrices in which one row after another is written and one column after another is read. These matrices are generally very large, for example of a size 256xc3x97256.
According to another method, in an article entitled xe2x80x9cWeight distributions for turbo-codes using random and nonrandom permutationsxe2x80x9d published by Jet Propulsion Laboratory, with xe2x80x9cTDA Progress Reportxe2x80x9d, number 42-122, of Aug. 15, 1995, Messrs. DOLINAR and DIVSALAR considered the permutations which, by numbering the k information positions between 0 and kxe2x88x921, move the binary information placed at a position i to a position e i+f, for xe2x80x9cwell chosenxe2x80x9d values of e and f.
In this document, they give only one example where k is a power of 2. In addition, they do not discuss the possible reciprocal influence of the choice of the permutation device and of that of the elementary convolutional coders (2, 1) to be used to generate the coded sequences produced by the turbocoder (3, 1).
The evaluation of the corresponding turbocode consists of simulating its use on a transmission channel with different signal/noise ratio values and measuring the minimum value of this ratio for which a predetermined value of the probability of error on the binary values is reached.
However, the use of simulations as an evaluation tool can lead to a few problems.
For example, the permutation device with k=65536=256xc3x97256, mentioned above, is chosen, and a predetermined error probability equal to 10xe2x88x925 is chosen to simulate the performance of a turbocode using this device. Consequently the mean number of errors on the binary values per block of 256xc3x97256 will be close to 1, but it will not be known whether each binary information item has the same error probability. This error probability could be fairly high for binary values having an xe2x80x9cunluckyxe2x80x9d position in the permutation device and this probability could be much smaller for more xe2x80x9cluckyxe2x80x9d positions.
A possible method for remedying this situation is to produce a harmonious and conjoint design of the permutation device and the two convolutional coders in order to guarantee a reasonable uniformity of the error rate on the binary values after decoding, as a function of the position of the binary information in the permutation device.
Another problem concerns the lack of algebraic tools for specifying the permutation devices. It will be useful to have available means for specifying a selection of permutation devices having a performance representative of the set of all the permutation devices.
The invention concerns principally the transmission of information represented by sequences of binary symbols:
u=(u0, u1, . . . , ukxe2x88x921),
referred to as xe2x80x9csequences of informationxe2x80x9d, which will be coded in a triplet of binary sequences,
v=(a, b, c),
each of these sequences a, b and c, being, by itself, representative of the sequence u.
In the remainder of the description, in order to represent a sequence u, the form u=(u0, u1, . . . , ukxe2x88x921), is used indifferently along with the associated polynomial form:
u(x)=u0x0+u1x1+. . . +ukxe2x88x921xkxe2x88x921.
Equivalent notations will be used for the sequences a, b and c. Using this second representation, its is known, in order to determine the triplet v=(a, b, c):
to choose a(x)=u(x);
to choose b(x)=u(x).h1(x)/g(x),
where g(x) is the polynomial, for example g(x)=1+x+x3, corresponding, according to the representation in a sequence, to the sequence (1, 1, 0, 1); and h1(x) is a polynomial, for example h1(x)=1+x+x2+x3, corresponding to the sequence (1, 1, 1, 1); and
by calling a* a sequence formed by permutation of the binary data of the sequence a, to choose c(x)=a*(x).h2(x)/g(x)
where h2(x) is a polynomial, for example h2(x)=(1+x2+x3) corresponding to the sequence (1, 0, 1, 1).
Any choice of the polynomials g(x), h1(x), h2(x) and of the permutation specifying the interlacer which associates the permuted sequence a* with the sequence a, specifies a coder which will be referred to as a xe2x80x9cturbocoderxe2x80x9d. All the sequences which a specified turbocoder can produce will be referred to as xe2x80x9cturbocodexe2x80x9d.
In the remainder of the description, the term xe2x80x9cfirst coderxe2x80x9d, will be given to the elementary recursive convolutional coder which produces the sequence b and xe2x80x9csecond coderxe2x80x9d will be given to the one which produces the sequences c.
The polynomial divisions used are of the type consisting of division according to ascending powers, well known to persons skilled in the art. They use modulo 2 arithmetic. The sequences a, b and c are binary sequences and in the general case the divisions which define b and c have a remainder.
This type of coding method has the advantage of lending itself to an iterative decoding which is powerful, relatively simple and inexpensive.
To implement it, several questions are posed.
I/ How to choose the polynomials g(x), h1(x) et h2(x)?
II/ How to choose the permutation of the terms of the sequence a which produces the sequence a*? Amongst the choices proposed, three examples of interlacers, that is to say of operators which permute the terms of the sequence a*, in order to form the sequence a*, are given below;
A) in the first example, after having arranged the terms of a in a rectangular table, successively row by row and, for each row, from left to right, the sequence a* is formed by taking the terms in this table in succession column after column and, for each column, from top to bottom. For example, in the case of sequences of six terms and the use of a table of two rows of three columns, the interlacer transforms the sequence a=(a0, a1, a2, a3, a4, a5) into the sequence a*=(a0, a3, a1, a4, a2, a5).
B) in a second example, the i-th term (i=0, 1, 2, . . . ) a*i of the sequence a* is chosen as being the term aj of the sequence a, with j=s.i+t calculated modulo the number of terms in the sequence a, s and t being integers. For example, if the number of terms of the sequence a is six and if s=5 and t=3, the interlacer transforms the sequence, a=(a0, a1, a2, a3, a4, a5) into the sequence a*=(a3, a2, a1, a0, a5, a4).
C) in the third example, the permutation chosen is random.
III/ How to avoid the division defining b(x) not having a remainder? and
IV/ How to avoid the division defining c(x) having a remainder?
Responding to these last two questions amounts to resolving a problem frequently mentioned in the literature on turbocodes, which is that of the xe2x80x9creturn to the zero statexe2x80x9d of the elementary convolutional coders defining b and c. Since the turbocoders have two elementary recursive coders, the second of which uses a permutation a* of the sequence a, it is wished to guarantee that the polynomials a(f) and a*(x) representing the information sequence u(x) are simultaneously divisible by g(x). Ensuring this divisibility condition for a(x) is simple since it suffices to construct a(x) from u(x) whilst supplementing u(x) with padding symbols in a number equal to the degree of g(x) and whose only function is to guarantee the absence of a remainder in the division serving to produce b(x) from a(x).
Choosing a permutation producing a*(x) from a(x) which guarantees both the divisibility of a*(x) by g(x) and good error correction performances for the turbocode thus specified is, on the other hand, more difficult.
This problem can give rise to disparities between the probabilities of errors after decoding of the different bits constituting u(x).
In an article which appeared in volume 31 No 1 of the journal xe2x80x9cElectronics Lettersxe2x80x9d of Jan. 5, 1995, Messrs. BARBULESCU and PIETROBON disclosed that an interlacer can be described by successively and cyclically arranging the terms of the sequence a in a number of sequences equal to the degree of the polynomial g(x) incremented by one, and that, in such case, permutations internal to each of the sequences thus formed give rise to equality between remainder of the division defining the sequence b and that of the division defining the sequence c.
However, and contrary to what is stated in this article, this statement is true only if the polynomial g(x) is of the form xcexa3i=0 to m xi.
In an article entitled xe2x80x9cTurbo-block-codesxe2x80x9d, published with the reports of the seminar xe2x80x9cTurbo Codingxe2x80x9d organised by the Institute of Technology of Lund (Sweden) (Department of Applied Electronics) in August 1996, Messrs C. BERROU, S. EVANO and G. BATTAIL disclosed that, by arranging the terms of the sequence u, cyclically, in a number of columns equal to a multiple of the degree N0 of the polynomial of type xnxe2x88x921 of the lowest strictly positive degree which is divisible by g(x), permutations internal to each of the columns thus formed mean that the sum of the remainder of the division defining the sequence b and of that of the division defining the sequence c is nil, so that the concatenation of the sequences is divisible by g.
This document, just like the previous one, therefore restricts the choice of the interlacers to particular forms working independently on sub-sets of the terms of the sequence a by applying internal permutations to them. It does not however guarantee that individually a(x) and a*(x) are divisible by g(x). The only thing that is guaranteed is the divisibility by g(x) of the polynomial representing the concatenation (a, a*), consisting of putting the two sequences a and a* end to end.
There results a possible loss of efficacy of the decoder since the latter is not informed of the state which the coder had at the moment marking the end of the calculation of b and the start of the calculation of c.
None of the articles cited proposes an effective choice of interlacer.
The present invention sets out to remedy these drawbacks by proposing on the one hand families of interlacers which guarantee return to zero at the end of the sequence c, when the sequence b returns to zero, and on the other hand proposing a choice of interlacers which is wider than that proposed by the articles cited above.
To this end, according to a first aspect, the present invention relates to a coding method characterised in that:
1/ it takes into account:
a predetermined integer M1, equal to or greater than 2,
a number K, greater than or equal to 1, of sequences a1 (i=1, . . . , K) of binary data representing a physical quantity, each sequence a, having:
a polynomial representation ai(x) which is a multiple of a predetermined polynomial gi(x), and
a number of binary data equal to the product of any integer number M and the integer N0, the smallest integer such that the polynomial xN0+1 is divisible by each of the polynomials g1(x);
2/ it includes a first operation of producing a number K*M1 of so-called xe2x80x9cpermutedxe2x80x9d sequences aij*, (i=1, . . . , K; j=1, . . . , M1), each sequence aij*
being obtained by a permutation of the corresponding sequence aj, said permutation being, in a representation where the binary data of each sequence ai are written, row by row, in a table with N0 columns and M rows, the resultant of any number of so-called elementary permutations which, each:
either has the property of transforming the cyclic code of length N0 and with a generator polynomial g1(x) into an equivalent cyclic code with a generator polynomial g1j(x) which can be equal to gi(x), and acts by permutation on the N0 columns of the table representing ai,
or is any permutation of the symbols of a column of said table; and
having, in consequence, a polynomial representation ij(x) which is equal to a polynomial product cij(x)gij(x),
at least one permuted sequence aij* being different from the corresponding sequence ai,
3/ it includes a second operation of producing M1 redundant sequences whose polynomial representation is equal to xcexa3fij(x) cij(x), for j=1, . . . , M1, each polynomial fij(x) being a polynomial with a degree at most equal to the degree of the polynomial gij(x) with the same indices i and j.
There have been introduced above, in a representation where the binary data of the sequence a are classified in a table of N0 columns and M rows, the successions of permutations taken from all the permutations including, on the one hand, the automorphisms of the binary cyclic code of length N0 and with a generator polynomial g(x), permuting with each other at least two of the N0 columns of the table and, on the other hand, the permutations working solely on data in the same column and permuting with each other at least two of the said data.
The inventors have discovered that all these successions of permutations, and only these, guarantee that, for any polynomial a(x) whose division by g(x) leaves a nil remainder, the permuted polynomial a*(x) has the same property.
For the study of the conditions governing the choice of gij, the reader can refer to page 234 of the book by Mrs F. J. MACWILLIAMS and Mr N. J. A. SLOANE xe2x80x9cThe theory of error-correcting codesxe2x80x9d published by North-Holland in 1977 and whose seventh impression was printed in 1992).
All choices described in the present invention include the interlacers disclosed in the two articles mentioned above. Thus the performance expressed in terms of error rate as a function of the signal/noise ratio can be improved without increasing the complexity of the turobcoder or that of the turbodecoder.
According to a second aspect, the present invention relates to a coding method characterised in that:
1/ it takes into account:
a predetermined integer M1, equal to or greater than 2,
a number K, greater than or equal to 1, of sequences aj(i=1, . . . , K) of binary data representing a physical quantity, each sequence ai having:
a polynomial representation ai(x) which is a multiple of a predetermined polynomial gi(x) and has no multiple polynomial factors, and
a number of binary data equal to the product of any odd integer number M and the integer N0, the smallest integer such that the polynomial xN0+1 is divisible by each of the polynomials gi(x);
2/ it includes a first operation of producing a number K*M1 of so-called xe2x80x9cpermutedxe2x80x9d sequences aij*, (i=1, . . . , K; j=1, . . . , M1), each sequence aij* having a polynomial representation equal to aij*(x)=ai*(xeij) modulo (xn+1), where
n is the product of the number M and the integer N0,
eij is a relatively prime number with n
cij is the quotient of aij*(x) by gij(x),
the polynomial gij(x) is the generator polynomial of the smallest cyclic code of length N0 containing the polynomial gi(xeij) modulo (xN0+1),
xe2x80x83at least one permuted sequence aij* being different from the corresponding sequence ai;
3/ it includes a second operation of producing M1 redundant sequences whose polynomial representation is equal to xcexa3fij(x) cij(x), for j=1, . . . , M1 each polynomial fij(x) being a predetermined polynomial with a degree at least equal to the degree of the polynomial gij(x) with the same indices i and j.
It should be noted here that it is then stated that e belongs to the cycle of 2, modulo M.N0.
By virtue of these provisions, on the one hand the majority of the columns in the table can be moved by permutation, and on the other hand, in this restricted choice, the minimum distance of the turbocode is more easily analysable and can therefore be optimised.
This second aspect of the invention has the same advantages as the first aspect.
The inventors observed that implementing the method of the present invention, in each of its aspects, as disclosed above, has the advantage that any error estimation by the corresponding decoder converges. The case where the error estimation does not converge is therefore excluded by the implementation of the present invention.
According to particular characteristics, during the first production operation, all the values of the exponents eij having same value of the index j are identical.
By virtue of these provisions, the coding method to which the present invention relates makes it possible to effect all the interlacings to j fixed in the same way. It is therefore simple to implement.
According to particular characteristics, during the first production operation, all the values of the exponents eij are equal to a power of 2.
By virtue of this provision, the polynomials gij are all identical.
According to particular characteristics, the coding method to which the present invention relates, as briefly disclosed above, includes an operation of transmitting on the one hand sequences ai, and, on the other hand, a sub-set of the data of the other sequences.
By virtue of these provisions, the efficiency of the method is increased.
According to a third aspect, the present invention relates to a coding device characterised in that it includes a processing means adapted to:
1/ take into account:
a predetermined integer M1, equal to or greater than 2,
a number K, greater than or equal to 1, of sequences ai(j=1, . . . , K) of binary data representing a physical quantity, each sequence ai having:
a polynomial representation ai(x) which is a multiple of a predetermined polynomial gi(x), and
a number of binary data equal to the product of any integer number M and the integer N0, the smallest integer such that the polynomial xN0+1 is divisible by each of the polynomials gi(x);
2/ production of a number K*M1 of so-called xe2x80x9cpermutedxe2x80x9d sequences, aij*, (i=1, . . . , K; j=1, . . . , M1), each sequence aij*
being obtained by a permutation of the corresponding sequence, said permutation being, in a representation where the binary data of each sequence ai are written, row by row, in a table with N0 columns and M rows, the resultant of any number of so-called elementary permutations which, each:
either has the property of transforming the cyclic code of length N0 and with a generator polynomial g1(x) into an equivalent cyclic code with a generator polynomial gij(x) which can be equal to gi(x), and acts by permutation on the N0 columns of the table representing ai,
or is any permutation of the symbols of a column of said table; and
having, in consequence, a polynomial representation aij*(x) which is equal to a polynomial product cij(x)gij(x),
at least one permuted sequence aij* being different from the corresponding sequence ai,
3/ producing M1 redundant sequences whose polynomial representation is equal to xcexa3fij(x) cij(x), for j=1, . . . , M1, each polynomial fij(x) being a polynomial with a degree at least equal to the degree of the polynomial gij(x) with the same indices i and j.
According to a fourth aspect, the present invention relates to a coding device characterised in that it has a processing means adapted to:
1/ take into account:
a predetermined integer M1, equal to or greater than 2,
a number K, greater than or equal to 1, of sequences ai (j=1, . . . , K) of binary data representing a physical quantity, each sequence ai having,
a polynomial representation ai(x) which is a multiple of a predetermined polynomial gi(x) and has no multiple polynomial factors, and
a number of binary data equal to the product of any odd integer number M and the integer N0, the smallest integer such that the polynomial xN0+1 is divisible by each of the polynomials gi(x);
2/ produce a number K*M1 of so-called xe2x80x9cpermutedxe2x80x9d sequences aij*, (j=1, . . . , K; j=1 , . . . , M1), each sequence aij* having a polynomial representation equal to aij*(x)=ai*(xeij) modulo (xn+1), where
n is the product of the number M and the integer N0,
eij is a relatively prime number with n
cij is the quotient of aij*(x) by gij(x),
the polynomial gij(x) is the generator polynomial of the smallest cyclic code of length N0 containing the polynomial gi(xeij) modulo (xN0+1),
xe2x80x83at least one permuted sequence aij* being different from the corresponding sequence al;
3/ produce M1 redundant sequences whose polynomial representation is equal to xcexa3fij(x) cij(x), for j=1, . . . , M1, each polynomial fij(x) being a predetermined polynomial with a degree at least equal to the degree of the polynomial gij(x) with the same indices i and j.
According to a fifth aspect, the present invention relates to a decoding method characterised in that:
1/ it takes into account:
a predetermined integer M1, equal to or greater than 2,
a number K, greater than or equal to 1, of sequences ai (j=1, . . . , K) of binary data representing a physical quantity, each sequence aj having:
a polynomial representation ai(x) which is a multiple of a predetermined polynomial gi(x), and
a number of binary data equal to the product of any integer number M and the integer N0, the smallest integer such that the polynomial xN0+1 is divisible by each of the polynomials gi(x);
2/ it includes an operation of parallel turbodecoding of K sequences of symbols using the divisor polynomials gij(x).
3/ it includes, for each ai, M1 permutation operations at least one of which is not identity, each permutation being, in a representation where the binary data of each sequence ai are written, row by row, in a table with N0 columns and M rows, the resultant of any number of so-called elementary permutations which, each:
either has the property of transforming the cyclic code of length N0 and with a generator polynomial gi(x) into an equivalent cyclic code with a generator polynomial gij(x) which can be equal to gi(x), and acts by permutation on the N0 columns of the table representing ai,
or is any permutation of the symbols of a column of said table.
According to a sixth aspect, the present invention relates to a decoding method characterised in that:
1/ it takes into account:
a predetermined integer M1, equal to or greater than 2,
a number K, greater than or equal to 1, of sequences ai (j=1, . . . , K) of binary data representing a physical quantity, each sequence ai having:
a polynomial representation ai(x) which is a multiple of a predetermined polynomial gi(x) and which has no multiple polynomial factors, and
a number of binary data equal to the product of any odd integer number M and the integer N0, the smallest integer such that the polynomial xN0+1 is divisible by each of the polynomials gi(x);
2/ it includes an operation of parallel turbodecoding of K sequences of symbols using the divisor polynomials gij(x),
3/ the said parallel turbodecoding operation including a permutation operation producing so-called xe2x80x9cpermutedxe2x80x9d sequences, aij*, (i=1, . . . , K; j=1, . . . , M1), each permuted sequence aij* having a polynomial representation equal to aij*(x)=ai*(xeij) modulo (xn+1), where:
n is the product of the number M and the integer N0,
eij is a relatively prime number with n
cij is the quotient of aij*(x) by gij(x),
the polynomial gij(x) is the generator polynomial of the smallest cyclic code of length N0 containing the polynomial gl(xeij) modulo xN0+1),
xe2x80x83at least one permuted sequence being different from the corresponding sequence ai.
According to a seventh aspect, the present invention relates to a decoding device characterised in that it includes a processing means adapted:
1/ to take into account:
a predetermined integer M1, equal to or greater than 2,
a number K, greater than or equal to 1, of sequences
ai (i=1, . . . , K) of binary data representing a physical quantity, each sequence ai having:
a polynomial representation ai(x) which is a multiple of a predetermined polynomial gi(x), and
a number of binary data equal to the product of any integer number M and the integer N0, the smallest integer such that the polynomial xN0+1 is divisible by each of the polynomials gi(x);
2/ to perform an operation of parallel turbodecoding of K sequences of symbols using the divisor polynomials gij(x).
3/ to perform, for each ai, M1 permutation operations, at least one of which is not identity, each permutation being, in a representation where the binary data of each sequence ai are written, row by row, in a table with N0 columns and M rows, the resultant of any number of so-called elementary permutations which, each:
either has the property of transforming the cyclic code of length N0 and with a generator polynomial gi(x) into an equivalent cyclic code with a generator polynomial gij(x) which can be equal to gi(x), and acts by permutation on the N0 columns of the table representing ai,
or is any permutation of the symbols of a column of said table.
According to an eighth aspect, the present invention relates to a decoding device characterised in that it has a processing means adapted:
1/ to take into account:
a predetermined integer M1, equal to or greater than 2,
a number K, greater than or equal to 1, of sequences ai(j=1, . . . , K) of binary data representing a physical quantity, each sequence ai having:
a polynomial representation ai(x) which is a multiple of a predetermined polynomial gi(x) and has no multiple polynomial factors, and
a number of binary data equal to the product of any odd integer number M and the integer N0, the smallest integer such that the polynomial xN0+1 is divisible by each of the polynomials gl(x);
2/ to perform an operation of parallel turbodecoding of K sequences of symbols using the divisor polynomials gij(x).
3/ to effect a permutation operation producing so-called xe2x80x9cpermutedxe2x80x9d sequences, aij*, (i=1, . . . , K; j=1, . . . , M1), each permuted sequence aij* having a polynomial representation equal to aij*(x)=al*(xeij) modulo (xn+1), where:
n is the product of the number M and the integer N0,
eij is a relatively prime number with n
cij is the quotient of aij*(x) by gij(x),
the polynomial gij(x) is the generator polynomial of the smallest cyclic code of length N0 containing the polynomial gi(xeij) modulo (xN0+1),
xe2x80x83at least one permuted sequence aij* being different from the corresponding sequence ai.
The invention also relates to:
an information storage means which can be read by a computer or a microprocessor storing instructions of a computer program, characterised in that it enables the method of the invention as briefly disclosed above to be implemented, and
an information storage means which is removable, partially or totally, and which can be read by a computer or a microprocessor storing instructions of a computer program, characterised in that it enables the method of the invention as briefly disclosed above to be implemented.
The invention also relates to:
a device for processing signals representing speech, which includes a device as briefly disclosed above,
a data transmission device having a transmitter adapted to implement a packet transmission protocol, which includes a device as briefly disclosed above,
a data transmission device having a transmitter adapted to implement the ATM (Asynchronous Transfer Mode) packet transmission protocol, which has a device as briefly disclosed above,
a data transmission device having a transmitter adapted to implement the packet transmission protocol, on a network of the ETHERNET (registered trade mark) type,
a network station, which has a device as briefly disclosed above,
a data transmission device having a transmitter transmitting on a non-cable channel, which has a device as briefly disclosed above, and
a device for processing sequences of signals representing at most one thousand binary data, which has a device as briefly disclosed above.
As these coding and decoding devices, these coding and decoding methods and these signal processing, data transmission and sequence processing devices and this network have the same particular characteristics and the same advantages as the coding method as briefly disclosed above, these particular characteristics and these advantages will not be repeated here.